// https://www.lintcode.com/problem/fast-power/?_from=ladder&&fromId=6

class Solution {
public:
    /**
     * @param a: A 32bit integer
     * @param b: A 32bit integer
     * @param n: A 32bit integer
     * @return: An integer
     */

    // 当n足够大的时候，a^n会很大，超出了表达范围
    // 这里主要使用了模运算的一个性质
    // (ab)%c = (a%c)(b%c)%c

  
    int fastPower(int a, int b, int n) {
        if (n == 0) return 1 % b;
        if (n == 1) return a % b;
        long long tmp = fastPower(a, b, n / 2);
        long long result = tmp * tmp % b;
        if (n % 2 == 0) return result;
        else return (result * (a % b)) % b;
    }
};